{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Exponential speedup with the Deutsch-Jozsa algorithm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Introduction\n",
    "\n",
    "The Deutsch-Jozsa algorithm[[1](#DJWiki)], named after David Deutsch and Richard Jozsa, is one of the fundamental and first quantum algorithms showing exponential speedup over their classical counterpart$^*$. While it has no practical applicative usage, it serves as a toy model for quantum computing, demonstrating how the concepts of super-position and interference enable quantum algorithms to overperform classical ones.\n",
    "\n",
    "$^*$ The exponential speedup is in the oracle complexity setting. In addition, it only refers to determenistic classical machines (see comments below).\n",
    "\n",
    "The algorithm treats the following problem:\n",
    "* Consider a black-box boolean function $f(x)$ which acts on the integers in the range $[0, 2^{n}-1]$.\n",
    "* It is guaranteed that the function is either constant or balanced ($\\equiv$ for half of the values it is 1 and for the other half 0).\n",
    "* The goal is to find in a deterministic way whether the function is constant or balanced.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Create our own implementation\n",
    "\n",
    "The circuit that we want to create is pictured below.\n",
    "To create this circuit we need to implement 4 steps:\n",
    "\n",
    "1. Declare and initialize a single auxiliary qubit called `aux`\n",
    "2. Apply the `hadamard_transform()` function on the qubits passed to the `main` function.\n",
    "3. create an oracle with the `phase_oracle()` function, this is the function signature: (if you are stuck more details are below) \n",
    "\n",
    "        def simple_oracle(\n",
    "            predicate: QCallable[QArray[QBit], QBit],\n",
    "            target: QArray[QBit],\n",
    "        )\n",
    "        \n",
    "4. Uncompute step 2 by applying the `hadamard_transform()` function to the \n",
    "\n",
    "Synthesize the circuit and execute in the IDE\n",
    "\n",
    "<details>\n",
    "<summary>\n",
    "Detailed instructions on using <code>phase_oracle()</code>\n",
    "</summary>\n",
    "The function takes two named inputs:\n",
    "\n",
    "1. predicate -> A `lambda` function with two inputs the target qubits and the auxiliary qubit, the expression will call the `my_black_box_prediate()`\n",
    "2. target -> The target qubit register\n",
    "</details>\n",
    "\n",
    "<br />\n",
    "\n",
    "<img src=\"\" />\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-05-07T14:26:56.085409Z",
     "iopub.status.busy": "2024-05-07T14:26:56.084110Z",
     "iopub.status.idle": "2024-05-07T14:27:01.550101Z",
     "shell.execute_reply": "2024-05-07T14:27:01.549100Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Opening: https://platform.classiq.io/circuit/48398168-acd9-4aa9-a9f3-c148338fb4ee?version=0.41.0.dev39%2B79c8fd0855\n"
     ]
    }
   ],
   "source": [
    "from classiq import *\n",
    "\n",
    "\n",
    "@qfunc\n",
    "def my_black_box_prediate(aux: QBit, target: QNum):\n",
    "    aux ^= target > 30\n",
    "\n",
    "\n",
    "@qfunc\n",
    "def main(target: Output[QNum]):\n",
    "    allocate(3, target)  # Allocate 3 qubits to the target register\n",
    "\n",
    "    pass\n",
    "\n",
    "\n",
    "qprog = synthesize(create_model(main))\n",
    "show(qprog)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Use within_apply\n",
    "\n",
    "Writing the Hadamard transform twice might not be ideal. Therefore there is a shorthand, namely `within_apply`, this will allow you to define the function between the two Hadamard transforms and even use other funcitons beside hadamerd transfrom to wrap this. Let's create the same function as above but use the `within_apply` function. \n",
    "\n",
    "<details>\n",
    "<summary>\n",
    "Detailed instructions on using <code>within_apply</code>\n",
    "</summary>\n",
    "The function takes two named inputs:\n",
    "\n",
    "1. compute -> A `lambda` function that holds the preparation and uncompute function. In this case the `hadamard_transform` function.\n",
    "2. action -> A `lambda` function that holds the action that is wrapped within the compute functions. In this case that is the entire `simple_oracle`.\n",
    "</details>\n",
    "\n",
    "<br />"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-05-07T14:27:01.585989Z",
     "iopub.status.busy": "2024-05-07T14:27:01.585252Z",
     "iopub.status.idle": "2024-05-07T14:27:03.833497Z",
     "shell.execute_reply": "2024-05-07T14:27:03.832712Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Opening: https://platform.classiq.io/circuit/4cf4b44d-b7ef-48f8-bbf4-554b07a7fae6?version=0.41.0.dev39%2B79c8fd0855\n"
     ]
    }
   ],
   "source": [
    "@qfunc\n",
    "def main(target: Output[QNum]):\n",
    "    allocate(3, target)  # Allocate 3 qubits to the target register\n",
    "\n",
    "    pass\n",
    "\n",
    "\n",
    "qprog = synthesize(create_model(main))\n",
    "show(qprog)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Mathematical explanation\n",
    "\n",
    "Below, we briefly go over the linear algebra behind the Deutsch-Jozsa algorithm. The first Hadamard transformation generates an equal superposition over all the standard basis elements:\n",
    "$$\n",
    "|0\\rangle_n \\xrightarrow[H^{\\otimes n}]{} \\frac{1}{2^{n/2}}\\sum^{2^n-1}_{j=0}|j\\rangle_n.\n",
    "$$\n",
    "Arithmetic oracle gets a boolean function and adds an $e^{\\pi i}=-1$ phase to all states for which the function returns True:\n",
    "$$\n",
    "\\frac{1}{2^{n/2}}\\sum^{2^n-1}_{j=0}|j\\rangle_n \\xrightarrow[\\text{Oracle}(f(j))]{}\\frac{1}{2^{n/2}}\\sum^{2^n-1}_{j=0}(-1)^{f(j)}|j\\rangle_n.\n",
    "$$\n",
    "Finally, we apply the Hadamard transform, which can be written as $H^{\\otimes n}\\equiv \\frac{1}{2^{n/2}}\\sum^{2^n-1}_{k,l=0}(-1)^{k\\cdot l} |k\\rangle \\langle l| $, to find\n",
    "$$\n",
    "\\frac{1}{2^{n/2}}\\sum^{2^n-1}_{j=0}(-1)^{f(j)}|j\\rangle  \\xrightarrow[H^{\\otimes n}]{} \n",
    "\\sum^{2^n-1}_{k=0} \\left(\\frac{1}{2^{n}}\\sum^{2^n-1}_{j=0}(-1)^{f(j)+j\\cdot k}|j\\rangle \\right) |k\\rangle.\n",
    "$$\n",
    "\n",
    "The probability of getting the state $|k\\rangle = |0\\rangle$ is\n",
    "$$\n",
    "P(0)=\\left|\\frac{1}{2^{n}}\\sum^{2^n-1}_{j=0}(-1)^{f(j)}|j\\rangle \\right|^2 =\n",
    "\\left\\{\n",
    "\\begin{array}{l l}\n",
    "1 & \\text{if } f(x) \\text{ is constant} \\\\\n",
    "0 & \\text{if } f(x) \\text{ is balanced}\n",
    "\\end{array}\n",
    "\\right.\n",
    "$$\n",
    "\n",
    "## Comments\n",
    "\n",
    "If we do not require deterministic determination, namely, we can apply a classical probabilistic algorithm to get the result up to some error, then we lose the exponential speedup: taking $k$ classical evaluations of the function $f$ determines whether the function is constant or balanced, with a probability $1-1/2^k$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The full solution for your reference"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-05-07T14:27:03.838462Z",
     "iopub.status.busy": "2024-05-07T14:27:03.837270Z",
     "iopub.status.idle": "2024-05-07T14:27:06.301508Z",
     "shell.execute_reply": "2024-05-07T14:27:06.300732Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Opening: https://platform.classiq.io/circuit/051aa7e3-4453-4faf-94cf-9bdb2b22761d?version=0.41.0.dev39%2B79c8fd0855\n"
     ]
    }
   ],
   "source": [
    "@qfunc\n",
    "def my_black_box_prediate(aux: QBit, target: QNum):\n",
    "    aux ^= target > 40\n",
    "\n",
    "\n",
    "@qfunc\n",
    "def main(target: Output[QNum]):\n",
    "    allocate(3, target)  # Allocate 3 qubits to the target register\n",
    "\n",
    "    aux = QBit(\"aux\")\n",
    "    allocate(1, aux)\n",
    "\n",
    "    within_apply(\n",
    "        compute=lambda: hadamard_transform(target=target),\n",
    "        action=lambda: phase_oracle(\n",
    "            predicate=lambda target, aux: my_black_box_prediate(aux=aux, target=target),\n",
    "            target=target,\n",
    "        ),\n",
    "    )\n",
    "\n",
    "    free(aux)\n",
    "\n",
    "\n",
    "qprog = synthesize(create_model(main))\n",
    "show(qprog)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
